home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group93b.txt / 000055_icon-group-sender _Fri Apr 30 02:31:13 1993.msg < prev    next >
Internet Message Format  |  1993-06-16  |  5KB
  1. Received: by cheltenham.cs.arizona.edu; Tue, 4 May 1993 05:07:11 MST
  2. Date: 30 Apr 93 02:31:13 GMT
  3. From: gudeman@arizona.edu  (David Gudeman)
  4. Organization: U of Arizona CS Dept, Tucson
  5. Subject: Summary: Representations of Dynamic Type Information
  6. Message-Id: <38557@optima.cs.arizona.edu>
  7. Sender: icon-group-request@cs.arizona.edu
  8. To: icon-group@cs.arizona.edu
  9. Status: R
  10. Errors-To: icon-group-errors@cs.arizona.edu
  11.  
  12. Well, thanks for all of the responses.  I got several new ideas, and
  13. got reminded of several things I had forgotten to include.  It would
  14. be a little impractical for me to "summarize" the entire report here,
  15. since it is 26 pages long.  However, there is a fairly complete draft
  16. available (at 26 pages it ought to be fairly complete :-), and if
  17. anyone is interested in reading it, it is available in compressed
  18. postscript by anonymous ftp from cs.arizona.edu in the file
  19. "/usr/ftp/janus/jc/tags.ps.Z".  If anyone has trouble getting this or
  20. needs an uncompressed file, or wants the latex source, let me know.  I
  21. haven't had time to discuss all of the ideas I got from the net, so
  22. I've included draft notes in the text to give a hint about these (and
  23. I've tried to credit the people who wrote me).  A few of the draft
  24. notes are essentially the remainders of my outline.  Since I have to
  25. go on to other work, the report is probably going to remain in this
  26. unfinished state for a while.
  27.  
  28. For those who are curious, but not curious enough to read a 26-page
  29. report, here is a rough outline of the methods (this does not include
  30. all of the tricks and special cases)
  31.  
  32. tagged-words (type information is in the machine word)
  33.   tag fields (word is broken up into tag and data fields)
  34.     tag field in high end (most-significant bits) of word
  35.        use tag of all zeros for one type to avoid tagging cost
  36.        negative ints get a tag of all ones, non-negative ints
  37.                                   get a tag of all zeros
  38.        use sign bit for one type
  39.          use sign-bit = 0 for one type and optimize another type by
  40.                                   giving it the tag of all ones in the
  41.                                   high end and tagging by negation.
  42.     tag field in low end of word
  43.       use n-bit tags to represent pointers data aligned on n-byte boundaries
  44.                                   this allows tagging without shifting
  45.         use a tag of all zeros to avoid tagging and untagging
  46.       use tags that contain only one non-zero bit to make testing faster
  47.       use all zeros to optimize integer arithmetic
  48.       optimize integer arithmetic by adding/subtracting tag
  49.                                   after subtraction/addition
  50.     tag field in both ends of word
  51.        various combinations of tricks from the other two options
  52.   partitioning by pattern (type is encoded in the representation of the value,
  53.                            no boxing/unboxing is done, usually words are
  54.                            partitioned into ranges of numbers they rep.)
  55.     simple range tests to identify types
  56.     segments with statically determined types (a segment is a range of
  57.                            numbers that can be identified by an
  58.                            initial field in the bit-patterns used to
  59.                            represent them).
  60.     segments with dynamically determined types
  61.       use BIBOP (table indexed by segments) to identify types
  62.       identify type in the segment itself
  63.         first word of segment
  64.         last word of segment
  65.       on a segmented architecture like the 80x86, one location has
  66.                            many addresses so the (machine) segment
  67.                            part of the address can be set to the
  68.                            (representation) segment of the data type
  69.                            being represented, and the offset can be
  70.                            set in such a way that any object can be in
  71.                            any machine segment.
  72.       on machines that ignore the high bits of pointer, these bits can
  73.                            be used for free boxing/unboxing
  74.   make everything a legal IEEE float, using the NaN bit patterns to
  75.                            encode all other types of data.
  76.  
  77. object-pointers (untagged pointers refering to self-identifying blocks
  78.                  on the heap)
  79.   combinations of this scheme with the tagged-word scheme
  80.  
  81. descriptors (two-word data elements divided into a type word and a
  82.              value word)
  83.   encoding a qualifier (address+length representation of a sequence)
  84.                            in a descriptor
  85.   encoding a cons cell in a descriptor
  86.   direct representation of floats
  87.  
  88. segregated type codes (type information is kept elsewhere)
  89.   type information for globals kept in a global area
  90.   type information for locals kept in stack frame
  91.   type information kept in header of aggregate objects
  92.  
  93. Thanks to Paul Tarau, Richard Fateman, Mikael Pettersson, Nick
  94. Thompson, Andrew Wright, Benjamin Goldberg, Aubrey Jaffer, Eric
  95. Benson, Marc Brandis, Kelvin Nilsen, Stavros Macrakis, Alexandr
  96. Kopilovich, Pekka Pirinen, William Griswold, David Keppel,
  97. Marc-Michael Brandis, Mark Tillotson, Richard Brooksby,
  98. cowan@magpie.linknet.com, Hintermeier Claus, Hendrik Boom, and Tim
  99. Lindholm for your help.
  100. -- 
  101.                     David Gudeman
  102. gudeman@cs.arizona.edu
  103.